class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        vector<int> f(n);
        auto g = f;
        f[0] = nums[0];
        g[0] = 0;

        for(int i = 1; i < n; i++)
        {
            f[i] = g[i-1] + nums[i];
            g[i] = max(f[i-1], g[i-1]);
        }
        return max(f[n-1],g[n-1]);
    }
};

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        // 两种情况下的最大值(选第一个和不选第一个)
        return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
    }

    int rob1(vector<int>& nums, int l, int r) {
        if (l > r)
            return 0;
        int n = nums.size();
        vector<int> f(n);
        auto g = f;

        // 初始化
        f[l] = nums[l];
        g[l] = 0;

        for (int i = l + 1; i <= r; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[r], g[r]);
    }
};

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        // 最主要的是预处理这一步工作，处理完就是完全的打家劫舍问题了：
        // 预处理：
        auto a = nums;
        sort(a.begin(), a.end());
        int n = *(a.end() - 1) + 1; // 找出nums中的最大的那个数，用于开空间

        vector<int> arr(n);
        for(auto x : nums) arr[x] += x; // 映射处理

        // 处理完后就是打家劫舍1的解题了：
        vector<int> f(n);
        auto g = f;

        f[0] = arr[0];
        g[0] = 0;

        for(int i = 1; i < n; i++)
        {
            f[i] = g[i - 1] + arr[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        return max(f[n - 1], g[n - 1]);
    }
};
class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();

        // n + 1：增加虚拟节点
        vector<vector<int>> dp(n + 1, vector<int>(3));
        for(int i = 1; i <= n; i++)
        {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
        }

        return min(dp[n][0], min(dp[n][1], dp[n][2]));
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3));

        // 只需初始化dp[0][0]即可，因为其他两在开表的时候默认为0
        dp[0][0] = -prices[0];

        for(int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }

        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<int> f(n, 0);
        auto g = f;
        f[0] = -prices[0];

        for (int i = 1; i < n; i++) {
            f[i] = max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);
        }

        return g[n - 1];
    }
};

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0, 0] for _ in range(n)]
        dp[0] = [-prices[0], 0]
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], - prices[i])
            dp[i][1] = max(dp[i-1][1], + prices[i] + dp[i-1][0])
        return dp[-1][-1]

class Solution {
public:
    const int N = 0x3f3f3f3f; // INT_MAX的一半
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, -N));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j >= 1) {
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int _max = 0;
        for (int i = 0; i < 3; i++) {
            _max = max(_max, g[n - 1][i]);
        }

        return _max;
    }
};

class Solution {
public:
    const int N = 0x3f3f3f3f;
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(k + 1, -N));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k + 1; j++) {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j >= 1) {
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int _max = 0;
        for (int i = 0; i < k + 1; i++) {
            _max = max(_max, g[n - 1][i]);
        }

        return _max;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        vector<int> dp(n);
        dp[0] = nums[0];

        for(int i = 1; i < n; i++)
        {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
        }

        int _max = INT_MIN;
        for(int i = 0; i < n; i++)
        {
            _max = max(_max, dp[i]);
        }
        return _max;
    }
};

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        vector<int> leftMax(n);
        // 对坐标为 0 处的元素单独处理，避免考虑子数组为空的情况
        leftMax[0] = nums[0];
        int leftSum = nums[0];
        int pre = nums[0];
        int res = nums[0];
        for (int i = 1; i < n; i++) {
            pre = max(pre + nums[i], nums[i]);
            res = max(res, pre);
            leftSum += nums[i];
            leftMax[i] = max(leftMax[i - 1], leftSum);
        }

        // 从右到左枚举后缀，固定后缀，选择最大前缀
        int rightSum = 0;
        for (int i = n - 1; i > 0; i--) {
            rightSum += nums[i];
            res = max(res, rightSum + leftMax[i - 1]);
        }
        return res;
    }
};


class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];

        vector<int> f(n);
        auto g = f;
        f[0] = nums[0];
        g[0] = nums[0];

        int sum = nums[0], fmax = -0x3f3f3f3f, gmin = 0x3f3f3f3f;
        for(int i = 1; i < n; i++)
        {
            f[i] = max(nums[i], f[i - 1] + nums[i]);
            fmax = max(fmax, f[i]);
            g[i] = min(nums[i], g[i - 1] + nums[i]);
            gmin = min(gmin, g[i]);
            sum += nums[i];
        }
        return sum == gmin ? fmax : max(fmax, (sum - gmin));
    }
};
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        auto g = f;
        f[0] = nums[0]; g[0] = nums[0];

        for(int i = 1; i < n; i++)
        {
            f[i] = max(nums[i], max(f[i - 1] * nums[i], g[i - 1] * nums[i]));
            g[i] = min(nums[i], min(f[i - 1] * nums[i], g[i - 1] * nums[i]));
        }

        int _max = INT_MIN;
        for(int i = 0; i < n; i++)
        {
            _max = max(_max, f[i]);
        }

        return _max;
    }
};

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1, 0);
        auto g = f;

        int _max = INT_MIN;
        for (int i = 1; i <= n; i++) {
            if (nums[i - 1] > 0) {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            } else if (nums[i - 1] < 0) {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            _max = max(_max, f[i]);
        }

        return _max;
    }
};

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        int sum = 0;
        for(int i = 2; i < n; i++)
        {
            dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;
            sum += dp[i];
        }

        return sum;
    }
};

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        vector<int> f(n, 1), g(n, 1);
        int _max = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] < arr[i - 1]) {
                g[i] = f[i - 1] + 1;
            } else if (arr[i] > arr[i - 1]) {
                f[i] = g[i - 1] + 1;
            }
            _max = max(_max, max(f[i], g[i]));
        }

        return _max;
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // 将字典中的单词映射到哈希表中，提升查找效率
        unordered_set<string> hash;
        for(auto& s : wordDict) hash.insert(s);

        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;
        s = ' ' + s; // 字符串前面加个辅助空格，这样可以使字符串下标和dp表下标是一一对应的
        for(int i = 1; i <= n; i++)
        {
            for(int j = i; j >= 1; j--)
            {
                if(dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
};


class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int n = s.size();
        vector<int> dp(n, 1);
        for (int i = 1; i < n; i++) {
            if (s[i - 1] + 1 == s[i] || s[i - 1] == 'z' && s[i] == 'a')
                dp[i] += dp[i - 1];
        }
 
        int hash[26] = {0};
        for (int i = 0; i < n; i++) {
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        }
        int sum = 0;
        for (auto i : hash)
            sum += i;
        return sum;
    }
};

class Solution {
public:
    const int N = 0x3f3f3f3f;
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(k + 1, -N));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k + 1; j++) {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j >= 1) {
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int _max = 0;
        for (int i = 0; i < k + 1; i++) {
            _max = max(_max, g[n - 1][i]);
        }

        return _max;
    }
};